Write a method to see if a binary tree ↴
A binary tree is a tree where every node has two or fewer children. The children are usually called left and right.
public class BinaryTreeNode {
public int value;
public BinaryTreeNode left;
public BinaryTreeNode right;
public BinaryTreeNode(int value) {
this.value = value;
}
}
This lets us build a structure like this:
That particular example is special because every level of the tree is completely full. There are no "gaps." We call this kind of tree "perfect."
Binary trees have a few interesting properties when they're perfect:
Property 1: the number of total nodes on each "level" doubles as we move down the tree.
Property 2: the number of nodes on the last level is equal to the sum of the number of nodes on all other levels (plus 1). In other words, about half of our nodes are on the last level.
Let's call the number of nodes n, and the height of the tree h. h can also be thought of as the "number of levels."
If we had h, how could we calculate n?
Let's just add up the number of nodes on each level! How many nodes are on each level?
If we zero-index the levels, the number of nodes on the xth level is exactly 2x.
So our total number of nodes is:
n=20+21+22+23+...+2h−1Why only up to 2h−1? Notice that we started counting our levels at 0. So if we have h levels in total, the last level is actually the "h−1"-th level. That means the number of nodes on the last level is 2h−1.
But we can simplify. Property 2 tells us that the number of nodes on the last level is (1 more than) half of the total number of nodes, so we can just take the number of nodes on the last level, multiply it by 2, and subtract 1 to get the number of nodes overall. We know the number of nodes on the last level is 2h−1, So:
n=2h−1∗2−1 n=2h−1∗21−1 n=2h−1+1−1 n=2h−1So that's how we can go from h to n. What about the other direction?
We need to bring the h down from the exponent. That's what logs are for!
First, some quick review. log10(100) simply means, "What power must you raise 10 to in order to get 100?". Which is 2, because 102=100.
We can use logs in algebra to bring variables down from exponents by exploiting the fact that we can simplify log10(102). What power must we raise 10 to in order to get 102? That's easy—it's 2.
So in this case we can take the log2 of both sides:
n=2h−1 n+1=2h log2((n+1))=log2(2h) log2(n+1)=hSo that's the relationship between height and total nodes in a perfect binary tree.
A tree is "superbalanced" if the difference between the depths of any two leaf nodes ↴
A leaf node is a tree node with no children.
It's the "end" of a path to the bottom, from the root.
Here's a sample binary tree node class:
public class BinaryTreeNode {
public int value;
public BinaryTreeNode left;
public BinaryTreeNode right;
public BinaryTreeNode(int value) {
this.value = value;
}
public BinaryTreeNode insertLeft(int leftValue) {
this.left = new BinaryTreeNode(leftValue);
return this.left;
}
public BinaryTreeNode insertRight(int rightValue) {
this.right = new BinaryTreeNode(rightValue);
return this.right;
}
}
Your first thought might be to write a recursive method, thinking, "the tree is balanced if the left subtree is balanced and the right subtree is balanced." This kind of approach works well for some other tree problems.
But this isn't quite true. Counterexample: suppose that from the root of our tree:
Both subtrees are balanced, but from the root we will have leaves at 3 different depths.
We could instead have our recursive method get the array of distinct leaf depths for each subtree. That could work fine. But let's come up with an iterative solution instead. It's usually better to use an iterative solution instead of a recursive one because it avoids stack overflow. ↴
The call stack is what a program uses to keep track of method calls. The call stack is made up of stack frames—one for each method call.
For instance, say we called a method that rolled two dice and printed the sum.
def roll_die():
return random.randint(1, 6)
def roll_two_and_sum():
total = 0
total += roll_die()
total += roll_die()
print total
roll_two_and_sum()
First, our program calls rollTwoAndSum(). It goes on the call stack:
rollTwoAndSum()
That function calls rollDie(), which gets pushed on to the top of the call stack:
rollDie()
rollTwoAndSum()
Inside of rollDie(), we call random.randint(). Here's what our call stack looks like then:
random.randint()
rollDie()
rollTwoAndSum()
When random.randint() finishes, we return back to rollDie() by removing ("popping") random.randint()'s stack frame.
rollDie()
rollTwoAndSum()
Same thing when rollDie() returns:
rollTwoAndSum()
We're not done yet! rollTwoAndSum() calls rollDie() again:
rollDie()
rollTwoAndSum()
Which calls random.randint() again:
random.randint()
rollDie()
rollTwoAndSum()
random.randint() returns, then rollDie() returns, putting us back in rollTwoAndSum():
rollTwoAndSum()
Which calls print():
print()
rollTwoAndSum()
What actually goes in a method's stack frame?
A stack frame usually stores:
Some of the specifics vary between processor architectures. For instance, AMD64 (64-bit x86) processors pass some arguments in registers and some on the call stack. And, ARM processors (common in phones) store the return address in a special register instead of putting it on the call stack.
Each method call creates its own stack frame, taking up space on the call stack. That's important because it can impact the space complexity of an algorithm. Especially when we use recursion.
For example, if we wanted to multiply all the numbers between 1 and n, we could use this recursive approach:
public static int product1ToN(int n) {
// we assume n >= 1
return (n > 1) ? (n * product1ToN(n-1)) : 1;
}
What would the call stack look like when n = 10?
First, product1ToN() gets called with n = 10:
product1ToN() n = 10
This calls product1ToN() with n = 9.
product1ToN() n = 9
product1ToN() n = 10
Which calls product1ToN() with n = 8.
product1ToN() n = 8
product1ToN() n = 9
product1ToN() n = 10
And so on until we get to n = 1.
product1ToN() n = 1
product1ToN() n = 2
product1ToN() n = 3
product1ToN() n = 4
product1ToN() n = 5
product1ToN() n = 6
product1ToN() n = 7
product1ToN() n = 8
product1ToN() n = 9
product1ToN() n = 10
Look at the size of all those stack frames! The entire call stack takes up O(n) space. That's right—we have an O(n) space cost even though our method itself doesn't create any data structures!
What if we'd used an iterative approach instead of a recursive one?
public static int product1ToN(int n) {
// we assume n >= 1
int result = 1;
for (int num = 1; num <= n; num++) {
result *= num;
}
return result;
}
This version takes a constant amount of space. At the beginning of the loop, the call stack looks like this:
product1ToN() n = 10, result = 1, num = 1
As we iterate through the loop, the local variables change, but we stay in the same stack frame because we don't call any other functions.
product1ToN() n = 10, result = 2, num = 2
product1ToN() n = 10, result = 6, num = 3
product1ToN() n = 10, result = 24, num = 4
In general, even though the compiler or interpreter will take care of managing the call stack for you, it's important to consider the depth of the call stack when analyzing the space complexity of an algorithm.
Be especially careful with recursive functions! They can end up building huge call stacks.
What happens if we run out of space? It's a stack overflow! In Java, you'll get a StackOverflowError.
If the very last thing a method does is call another method, then its stack frame might not be needed any more. The method could free up its stack frame before doing its final call, saving space.
This is called tail call optimization (TCO). If a recursive function is optimized with TCO, then it may not end up with a big call stack.
In general, most languages don't provide TCO. Scheme is one of the few languages that guarantee tail call optimization. Some Ruby, C, and Javascript implementations may do it. Python and Java decidedly don't.
We can do this in O(n) time and O(n) space.
What about a tree with only one leaf node? Does your method handle that case properly?
Sometimes it's good to start by rephrasing or "simplifying" the problem.
The requirement of "the difference between the depths of any two leaf nodes is no greater than 1" implies that we'll have to compare the depths of all possible pairs of leaves. That'd be expensive—if there are n leaves, there are O(n2) possible pairs of leaves.
But we can simplify this requirement to require less work. For example, we could equivalently say:
If you're having trouble with a recursive approach, try using an iterative one.
To get to our leaves and measure their depths, we'll have to traverse the tree somehow. What methods do we know for traversing a tree?
Depth-first ↴
Depth-first search (DFS) is a method for exploring a tree or graph. In a DFS, you go as deep as possible down one path before backing up and trying a different one.
Depth-first search is like walking through a corn maze. You explore one path, hit a dead end, and go back and try a different one.
Here's a how a DFS would traverse this tree, starting with the root:
We'd go down the first path we find until we hit a dead end:
Then we'd do the same thing again—go down a path until we hit a dead end:
And again:
And again:
Until we reach the end.
Depth-first search is often compared with breadth-first search.
Advantages:
Disadvantages
Breadth-first search (BFS) is a method for exploring a tree or graph. In a BFS, you first explore all the nodes one step away, then all the nodes two steps away, etc.
Breadth-first search is like throwing a stone in the center of a pond. The nodes you explore "ripple out" from the starting point.
Here's a how a BFS would traverse this tree, starting with the root:
We'd visit all the immediate children (all the nodes that're one step away from our starting node):
Then we'd move on to all those nodes' children (all the nodes that're two steps away from our starting node):
And so on:
Until we reach the end.
Breadth-first search is often compared with depth-first search.
Advantages:
Disadvantages
The worst-case time and space costs of both are the same—you could make a case for either.
But one characteristic of our algorithm is that it could short-circuit and return false as soon as it finds two leaves with depths more than 1 apart. So maybe we should use a traversal that will hit leaves as quickly as possible...
Depth-first traversal will generally hit leaves before breadth-first, so let's go with that. How could we write a depth-first walk that also keeps track of our depth?
We do a depth-first walk ↴
Depth-first search (DFS) is a method for exploring a tree or graph. In a DFS, you go as deep as possible down one path before backing up and trying a different one.
Depth-first search is like walking through a corn maze. You explore one path, hit a dead end, and go back and try a different one.
Here's a how a DFS would traverse this tree, starting with the root:
We'd go down the first path we find until we hit a dead end:
Then we'd do the same thing again—go down a path until we hit a dead end:
And again:
And again:
Until we reach the end.
Depth-first search is often compared with breadth-first search.
Advantages:
Disadvantages
Each time we hit a leaf with a new depth, there are two ways that our tree might now be unbalanced:
Why are we doing a depth-first walk and not a breadth-first ↴
Breadth-first search (BFS) is a method for exploring a tree or graph. In a BFS, you first explore all the nodes one step away, then all the nodes two steps away, etc.
Breadth-first search is like throwing a stone in the center of a pond. The nodes you explore "ripple out" from the starting point.
Here's a how a BFS would traverse this tree, starting with the root:
We'd visit all the immediate children (all the nodes that're one step away from our starting node):
Then we'd move on to all those nodes' children (all the nodes that're two steps away from our starting node):
And so on:
Until we reach the end.
Breadth-first search is often compared with depth-first search.
Advantages:
Disadvantages
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
private static class NodeDepthPair {
BinaryTreeNode node;
int depth;
NodeDepthPair(BinaryTreeNode node, int depth) {
this.node = node;
this.depth = depth;
}
}
public static boolean isBalanced(BinaryTreeNode treeRoot) {
// a tree with no nodes is superbalanced, since there are no leaves!
if (treeRoot == null) {
return true;
}
// we short-circuit as soon as we find more than 2
List<Integer> depths = new ArrayList<>(3);
Deque<NodeDepthPair> nodes = new ArrayDeque<>();
nodes.push(new NodeDepthPair(treeRoot, 0));
while (!nodes.isEmpty()) {
// pop a node and its depth from the top of our stack
NodeDepthPair nodeDepthPair = nodes.pop();
BinaryTreeNode node = nodeDepthPair.node;
int depth = nodeDepthPair.depth;
// case: we found a leaf
if (node.left == null && node.right == null) {
// we only care if it's a new depth
if (!depths.contains(depth)) {
depths.add(depth);
// two ways we might now have an unbalanced tree:
// 1) more than 2 different leaf depths
// 2) 2 leaf depths that are more than 1 apart
if (depths.size() > 2 || (depths.size() == 2
&& Math.abs(depths.get(0) - depths.get(1)) > 1)) {
return false;
}
}
// case: this isn't a leaf - keep stepping down
} else {
if (node.left != null) {
nodes.push(new NodeDepthPair(node.left, depth + 1));
}
if (node.right != null) {
nodes.push(new NodeDepthPair(node.right, depth + 1));
}
}
}
return true;
}
O(n) time and O(n) space.
For time, the worst case is the tree is balanced and we have to iterate over all n nodes to make sure.
For the space cost, we have two data structures to watch: depths and nodes.
depths will never hold more than three elements, so we can write that off as O(1).
Because we’re doing a depth first search, nodes will hold at most d nodes where d is the depth of the tree (the number of levels in the tree from the root node down to the lowest node). So we could say our space cost is O(d).
But we can also relate d to n. In a balanced tree, d is O(log2(n)). And the more unbalanced the tree gets, the closer d gets to n.
In the worst case, the tree is a straight line of right children from the root where every node in that line also has a left child. The traversal will walk down the line of right children, adding a new left child to nodes at each step. When the traversal hits the rightmost node, nodes will hold half of the n total nodes in the tree. Half is O(n), so our worst case space cost is O(n).
This is an intro to some tree basics. If this is new to you, don't worry—it can take a few questions for this stuff to come together. We have a few more coming up.
Particular things to note:
Focus on depth-first ↴
You should also be very comfortable coding each of them up.
One tip: Remember that breadth-first uses a queue ↴
| Worst Case | |
|---|---|
| space | O(n) |
| enqueue | O(1) |
| dequeue | O(1) |
| peek | O(1) |
A queue stores items in a first-in, first-out (FIFO) order.
Picture a queue like the line outside a busy restaurant. First come, first served.
Queues are easy to implement with linked lists:
You could implement a queue with an array or dynamic array, but it would get kinda messy. Try drawing it out. You'll notice that you'd need to build out a "scoot over" or "re-center" operation that automatically fires when your queue items hit the bottom edge of the array.
| Worst Case | |
|---|---|
| space | O(n) |
| push | O(1) |
| pop | O(1) |
| peek | O(1) |
A stack stores items in a last-in, first-out (LIFO) order.
Picture a pile of dirty plates in your sink. As you add more plates, you bury the old ones further down. When you take a plate off the top to wash it, you're taking the last plate you put in. "Last in, first out."
You can implement a stack with either a linked list or a dynamic array—they both work pretty well:
| Stack Push | Stack Pop | |
|---|---|---|
| Linked Lists | insert at head | remove at head |
| Dynamic Arrays | append | remove last element |
Java comes with a built in stack implementation , but it's better to use Deques instead.
The stack implementation has a few big drawbacks: it doesn't have an interface and it extends the Vector class, which has thread synchronization overhead.
Wanna review this one again later? Or do you feel like you got it all?
Wanna review this one again later? Or do you feel like you got it all?
Mark as done Pin for review laterWant more coding interview help?
Check out for more advice, guides, and practice questions.
Reset editor
Powered by qualified.io